package com.liuwei.spring.cloud.junit.leetcode.interview;

import com.liuwei.spring.cloud.common.utils.Maths;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;

public class RobSeven {

    public static void main(String[] args) {
        BigInteger result = get(10000);
        System.out.println("result:"+result);

        /*Map<String,BigInteger> cache = new HashMap<>();
        BigInteger f = factorial(cache,5);
        System.out.println("factorial:"+f);*/
    }

    public static BigInteger get(int start){
        int value = start -7;
        List<Metric> solutions = new ArrayList<Metric>();
        for (int i = 0; i <= value/2; i++) {
            int j = value-(i*2);
            if((i+j)%2==1){
                Metric number = new Metric();
                number.setOne(j);
                number.setTwo(i);
                number.setAmount(i+j);
                solutions.add(number);
            }
        }

        Map<String,BigInteger> cache = new HashMap<>();
        for (int i = 1; i <= 10000 ; i= i+200) {
            cache.put(String.valueOf(i),factorial(cache,i));
        }
        BigInteger total = BigInteger.ZERO;
        for (int i = 0; i < solutions.size(); i++) {
            Metric number = solutions.get(i);
            BigInteger possible = Cn(cache,number.amount,number.one);
            total = total.add(possible);
        }
        return total;
    }

    public static BigInteger Cn(Map<String,BigInteger> cache,int total,int m){
        return Maths.factorial(total).divide(Maths.factorial(m)).divide(Maths.factorial(total-m));
    }

    public static BigInteger factorial(Map<String,BigInteger> cache,int n){
        System.out.println("factorial n="+n);
        if(cache.containsKey(String.valueOf(n))){
            return cache.get(String.valueOf(n));
        }
        if(n<=1){
            cache.put(String.valueOf(1),BigInteger.ONE);
            return BigInteger.ONE;
        }
        BigInteger value = BigInteger.valueOf(n).multiply(factorial(cache,n-1));
        cache.put(String.valueOf(n),value);
        return value;
    }


    public static class Metric{
        int one;
        int two;
        int amount;

        public int getOne() {
            return one;
        }

        public void setOne(int one) {
            this.one = one;
        }

        public int getTwo() {
            return two;
        }

        public void setTwo(int two) {
            this.two = two;
        }

        public int getAmount() {
            return amount;
        }

        public void setAmount(int amount) {
            this.amount = amount;
        }
    }
}
